The present invention relates to a mass storage associative memory, which is divided into a plurality of associative memory subblocks, and an encoder, which is applied to this associative memory, for encoding addresses corresponding to hit flags as a result of match retrieval between retrieval data and the contents of each memory word or otherwise addresses corresponding to empty flags indicative of whether or not the contents of each memory word are valid as objects for match retrieval so that the addresses may efficiently be encoded in the predetermined priority order.
Heretofore, associative memories, that is, fully parallel CAMs (Content Addressable Memories), have been widely known as semiconductor storage devices having the functions of performing the match detection of retrieval data and stored data concurrently in terms of all bits and outputting the match address of stored data or stored data (see "Design of CMOS VLSI," pp 176-177, edited by Tetsuya Iizuka and supervised by Takuo Sugano, Baifukan, 1989).
Content-addressed retrieval, instead of retrieval by means of physical memory addresses, is common to content addressable memories (CAMs). Therefore, the basic function of CAM, unlike an ordinary memory, is to input retrieval data for example so as to output a word address at which data matching the retrieval data has been stored. However, only one word is not necessarily matching and there may be a plurality of them. When the plurality of match words are obtained like this, a correct encode output is unavailable with an ordinary encoder. Consequently, CAM is equipped with a priority encoder for encoding and outputting a plurality of match (hit) signals in the order of predetermined priorities.
In a bulk CAM, however, the number of words is generally very large in contrast to the word length. For this reason, a cell array is divided into a plurality of blocks and it is an important problem how priority encoders are arranged. In other words, the priority encoders will occupy a large area and power consumption will also be on the increase if the priority encoder is provided for every block of CAM. As the number of blocks increases because of the division of the array, the area thus occupied thereby and the power consumption proportionally increase further.
As a result, there has been proposed a content addressable memory in which one main priority encoder is provided for the plurality of blocks and a block priority encoder to be separately provided is used for the block in which encoding is carried out by the main priority encoder.
FIG. 30 shows such a content addressable memory (CAM). As shown in FIG. 30, the content addressable memory 200 is divided into four CAM blocks 202 and each CAM block 202 is further divided into eight CAM subblocks 204. A priority encoder 210 is structurally hierarchical in that there are installed four main priority encoders 212, each being intended for the CAM block 202 having eight of the CAM subblocks 204, and one subblock priority encoder 214 is provided every four CAM blocks 202. As shown in FIG. 31, further, the CAM subblock 204 comprises a CAM subarray 206 having a predetermined number of CAM words with predetermined word length and its control unit including a hit signal register 208 for holding a hit signal resulting from the hitting of retrieval data against a CAM word.
At the time of match retrieval in the CAM block 202, the hit signals of all words in each subblock 204 are held by the hit signal register 208 and a subblock hit signal indicating the presence of a match word in the subblock 204 is simultaneously generated by an OR circuit (not shown) of the control unit in each CAM subblock 204. On receiving the signal, the subblock priority encoder 214 subsequently generates a subblock selection signal indicating the highest priority CAM subblock 204 and the subblock priority encoder 214 also generates an encoded subblock address.
On receiving the block selection signal, a switch circuit (not shown) of the subblock thus selected is then activated to transfer the data (hit signal) held in the hit signal register 208 to the main priority encoder 212 as an output signal. Thereafter, the main priority encoder 212 generates a hit memory word address resulting from the hit signal thus transferred and encoded in the order of predetermined priorities in the CAM subblock 204. The priority encoder 210 combines the hit memory word address and the aforementioned subblock address and outputs the encoding logical address of the hit memory word of the CAM 200.
In the conventional CAM 200 shown in FIGS. 30 and 31, the priority encoder (encoder) 210 comprises the main priority encoder (priority encoder) 212 for controlling the plurality of CAM subblocks 204 and the subblock priority encoder 214 for assigning priority to the CAM subblocks 204 for performing the encoding operation. The order of priorities is first determined among the plurality of the subblocks 204 and before being encoded, the output signal of the first priority subblock 204 is applied to the main priority encoder 212. The encoder can thus be made relatively small in configuration, whereas the circuit area relative to the whole circuit scale of the CAM 200 is reduced, whereby large scale integration is made feasible.
Notwithstanding, subblock-to-subblock switch time becomes necessary until the encoding of the output signal (hit signal data (hereinafter called "flag data")) from the second priority CAM subblock 204 is started after the output signal (flag data) from the first priority subblock 204 is encoded by the main priority encoder 212 and output. In other words, it takes time to transfer the flag data from the hit signal register 208 of the second priority subblock 204 after an encoded address is output from the main priority encoder 212 and there still exists a problem arising from low encoding efficiency.
In an apparatus using an associative memory, on the other hand, the operation of updating the contents of a memory word is frequently performed by, for example, holding the contents of a plurality of memory words matching with retrieval data as a result of match retrieval and sequentially writing new data to the memory words that have been erased after the content of a memory word mismatching with retrieval data are erased in order to improve the use efficiency of each memory word of the associative memory.
In an apparatus such as a switching hub in which a plurality of computers are connected so as to build up an integrated network environment, for example, an associative memory is used to obtain additional data such as a port number corresponding to a MAC address existing in the header portion of packet data, based on which the packet data transferred from the source computer is output from a port corresponding to the port number obtained, whereby the additional data is properly transferred to a destination computer.
When a port for use in connecting a certain computer is changed from a port 1 to a port 3 in that case, unless the port number which is stored in the additional data of the memory word in which the data of a MAC address corresponding to this computer is stored, is updated from the port 1 to the port 3, packet data to be transferred to this computer is output from the port 1 to which this computer has been connected previously instead of the port 3 to which this computer is actually connected now. In order to prevent this trouble, the port number to which each computer has been connected should be updated thereon at all times.
Moreover, the number of memory words in an associative memory is generally smaller than the total number of computers on a network and only information of specific computers is selectively stored in each of the memory words. In order to improve the use efficiency of an associative memory, for example, time stamp information for managing an operating duration is stored in the additional data and the time stamp information is always updated, so that only the frequently-used computer information is registered in the memory word. Therefore, time stamp information on each memory word should be updated thereon at all times.
Thus, the operation of updating the contents of each memory word in an associative memory is frequently performed in an apparatus using an associative memory.
It is necessary to manage the address of the memory word whose contents have been erased so as to update the contents of each memory word in such an associative memory. However, the address of the memory word whose contents have been erased can't be managed in a conventional associative memory of the sort described above because the address of a memory word whose contents are to be erased occurs at random; the problem is that the address of the memory word whose contents have been erased has to be managed by something outside the associative memory, for example.